package org.maps;

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Created by oler on 20.08.14.
 */
public class MyHashMap implements MyMap {

    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private SimpleEntry[] table = {};

    int threshold;
    final float loadFactor;

    private int size;

    static class SimpleEntry implements MyMapEntry {

        final Object key;
        Object value;
        SimpleEntry next;
        int hash;

        SimpleEntry(int hash, Object key, Object value, SimpleEntry next) {
            this.value = value;
            this.next = next;
            this.key = key;
            this.hash = hash;
        }

        @Override
        public Object getKey() {

            return key;
        }

        @Override
        public Object getValue() {

            return value;
        }

        @Override
        public Object setValue(Object value) {
            Object oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        @Override
        public boolean equals(Object o) {

            if (!(o instanceof SimpleEntry)) {
                return false;
            }

            SimpleEntry e = (SimpleEntry) o;
            Object k1 = getKey();
            Object k2 = e.getKey();

            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2))) {
                    return true;
                }
            }
            return false;
        }

        @Override
        public final int hashCode() {
            return hash;
        }

        @Override
        public final String toString() {
            return getKey() + "=" + getValue();
        }
    }

    private class EntryIterator implements Iterator<Object> {

        int index;
        SimpleEntry current;
        SimpleEntry next;

        EntryIterator() {
            if (size > 0) {
                while (index < table.length && (next = table[index++]) == null) {
                }
                ;
            }
        }

        @Override
        public final boolean hasNext() {

            return next != null;
        }

        final SimpleEntry nextEntry() {

            SimpleEntry e = next;
            if (e == null) {
                throw new NoSuchElementException();
            }

            if ((next = e.next) == null) {
                while (index < table.length && (next = table[index++]) == null) {
                }
                ;
            }
            current = e;

            return e;
        }

        @Override
        public void remove() {

            if (current == null) {
                throw new IllegalStateException();
            }

            Object k = current.key;
            current = null;
            MyHashMap.this.remove(k);
        }

        @Override
        public Object next() {
            return nextEntry();
        }
    }

    /**
     * constructs an empty HashMap with the default initial
     * capacity (16) and the default loadFactor (0.75)
     */
    public MyHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    /**
     * constructs an empty HashMap with the specified initial
     * capacity and the default loadFactor (0.75)
     *
     * @param initialCapacity
     * @throws IllegalArgumentException if the initial capacity is negative
     */
    public MyHashMap(int initialCapacity) throws IllegalArgumentException {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * constructs an empty HashMap with the specified initial capacity
     * and loadFactor
     *
     * @param initialCapacity
     * @param loadFactor
     * @throws IllegalArgumentException if the initial capacity is negative or the loadFactor is non positive
     */
    public MyHashMap(int initialCapacity, float loadFactor)
            throws IllegalArgumentException {

        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal initial capacity: " +
                    initialCapacity);
        }
        if (initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        }

        if (loadFactor <= 0) {
            throw new IllegalArgumentException("Illegal load factor: " +
                    loadFactor);
        }

        this.loadFactor = loadFactor;
        this.threshold = initialCapacity;
    }

    @Override
    public void clear() {

        Arrays.fill(table, null);
        size = 0;
    }

    @Override
    public boolean containsKey(Object key) {

        return getEntry(key) != null;
    }

    @Override
    public boolean containsValue(Object value) {
        if (value == null) {
            return containsNullValue();
        }

        SimpleEntry[] tab = table;
        for (SimpleEntry aTab : tab) {
            for (SimpleEntry e = aTab; e != null; e = e.next) {
                if (value.equals(e.value)) {
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public Object get(Object key) {

        if (key == null) {
            return getForNullKey();
        }

        SimpleEntry entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

    @Override
    public boolean isEmpty() {

        return size == 0;
    }

    @Override
    public Object put(Object key, Object value) {

        if (table.length == 0) {
            inflateTable(threshold);
        }
        if (key == null) {
            return putForNullKey(value);
        }

        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (SimpleEntry e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                Object oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }

        addEntry(hash, key, value, i);

        return null;
    }

    @Override
    public Object remove(Object key) {

        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        int i = indexFor(hash, table.length);
        SimpleEntry prev = table[i];
        SimpleEntry result = prev;

        while (result != null) {
            SimpleEntry next = result.next;
            Object k;
            if (result.hash == hash &&
                    ((k = result.key) == key || (key != null && key.equals(k)))) {
                size--;
                if (prev == result) {
                    table[i] = next;
                } else {
                    prev.next = next;
                }
                break;
            }
            prev = result;
            result = next;
        }

        return (result == null ? null : result.value);
    }

    @Override
    public int size() {

        return size;
    }

    @Override
    public Iterator entryIterator() {

        return new EntryIterator();
    }

    private void inflateTable(int toSize) {

        int capacity = roundUpToPowerOf2(toSize);

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new SimpleEntry[capacity];
    }

    private void addEntry(int hash, Object key, Object value, int bucketIndex) {

        if ((size >= threshold) /*&& (null != table[bucketIndex])*/) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        SimpleEntry e = table[bucketIndex];
        table[bucketIndex] = new SimpleEntry(hash, key, value, e);
        size++;
    }

    private Object putForNullKey(Object value) {

        for (SimpleEntry e = table[0]; e != null; e = e.next) {

            if (e.key == null) {
                Object oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }
        addEntry(0, null, value, 0);
        return null;
    }

    private Object getForNullKey() {

        if (size == 0) {
            return null;
        }

        for (SimpleEntry e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                return e.value;
            }
        }

        return null;
    }


    private boolean containsNullValue() {

        for (SimpleEntry aTable : table) {
            for (SimpleEntry e = aTable; e != null; e = e.next) {
                if (e.value == null) {
                    return true;
                }
            }
        }
        return false;
    }

    private static int roundUpToPowerOf2(int number) {

        int rounded = number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (rounded = Integer.highestOneBit(number)) != 0
                ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
                : 1;

        return rounded;
    }

    private void resize(int newCapacity) {

        SimpleEntry[] oldTable = table;
        int oldCapacity = oldTable.length;

        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        SimpleEntry[] newTable = new SimpleEntry[newCapacity];

        int newCapacity0 = newTable.length;
        for (SimpleEntry e : table) {
            while (null != e) {
                SimpleEntry next = e.next;
                e.hash = null == e.key ? 0 : hash(e.key);

                int i = indexFor(e.hash, newCapacity0);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }

        table = newTable;
        threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

    private final int hash(Object k) {

        int h = k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    private static int indexFor(int h, int length) {
        return h & (length - 1);
    }

    private final SimpleEntry getEntry(Object key) {

        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        for (SimpleEntry e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {

            Object k;
            if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) {

                return e;
            }
        }
        return null;
    }

}
